package linkList;

public class N203_RemoveElement {

    public ListNode removeElements(ListNode head, int val) {
        // 删除头结点，保证头节点不是val
        while (head != null && head.val == val) head = head.next;
        // 从头结点的下一个结点开始，检查删除或者跳过检查下一个
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

    /**
     * 使用虚拟节点
     */
    public ListNode removeElements_VirtualNode(ListNode head, int val) {
        ListNode virtualHead = new ListNode(0, head);
        ListNode cur = virtualHead;
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }

        head = virtualHead.next;
        return head;
    }

    public static void main(String[] args) {
        N203_RemoveElement solution = new N203_RemoveElement();
        int val = 6;
        int[] arr = {1, 2, 6, 3, 4, 5, 6};
        ListNode head = ListNode.generaListByArray(arr);
        ListNode.printList(head);

        head = solution.removeElements_VirtualNode(head, val);
        ListNode.printList(head);
    }
}
